#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
/**
 * @brief
 * n == score.length
1 <= n <= 10^4
0 <= score[i] <= 106
All the values in score are unique.
 *
 * @return int
 */
class Solution
{
public:
    vector<string> findRelativeRanks(vector<int> &score)
    {
        int sorceLen = score.size();
        vector<string> ans(sorceLen, "");
        // backup score
        for (int i = 0; i < sorceLen; i++)
        {
            ans[i] = to_string(score[i]);
        }
        sort(score.rbegin(), score.rend());
        for (int i = 0; i < sorceLen; i++)
        {
            if (to_string(score[i]) == ans[i])
            {
                if (i == 0)
                {
                    ans[i] = "Gold Medal";
                }
                else if (i == 1)
                {
                    ans[i] = "Silver Medal";
                }
                else if (i == 2)
                {
                    ans[i] = "Bronze Medal";
                }
                else
                {
                    ans[i] = to_string(i + 1);
                }
            }
        }
        return ans;
    }

    vector<string> findRelativeRanks_2(vector<int> &score)
    {
        vector<string> ans(score.size());
        unordered_map<int, int> tmpMap;
        for (int i = 0; i < score.size(); i++)
        {
            tmpMap[score[i]] = i;
        }

        sort(score.begin(), score.end(), greater<int>());
        for (int i = 0; i < score.size(); i++)
        {
            if (i == 0)
            {
                ans[tmpMap[score[i]]] = "Gold Medal";
            }
            else if (i == 1)
            {
                ans[tmpMap[score[i]]] = "Silver Medal";
            }
            else if (i == 2)
            {
                ans[tmpMap[score[i]]] = "Bronze Medal";
            }
            else
            {
                ans[tmpMap[score[i]]] = to_string(i + 1);
            }
        }
        return ans;
    }
};
int main()
{
    Solution s;
    vector<int> score = {10, 3, 8, 9, 4};
    vector<string> ans = s.findRelativeRanks_2(score);
    for (string a : ans)
    {
        cout << a << " ";
    }
    cout << endl;
    system("pause");
    return 0;
}
